A communication network is a collection of network elements interconnected so as to support the transfer of information from a user at one network node to a user at another. The principal network elements are links and switches. A link transfers a stream of bits from one end to another at a specified rate with a given bit error rate and a fixed propagation time. The rate at which a buffer is served is the service capacity, measured in bits per second. Other common terms for service capacity are link-rate and bandwidth. Links are unidirectional. Important links are:                optical fibre;        copper coaxial cable;        microwave wireless.        
Several incoming and outgoing links meet at a switch, a device that transfers bits from its incoming links to its outgoing links. The name “switch” is used in telephony, while in computer communications, the device that performs routing is called a “router”; the terms are used interchangeably in this specification. When the rate of incoming bits exceeds that of outgoing bits, the excess bits are queued in a buffer at the switch. The receiver of each incoming link writes a packet of bits into its input buffer; the transmitter of each outgoing link reads from its output buffer. The switch transports packets from an input buffer to the appropriate output buffer. A schematic example of such a network arrangement is shown in FIG. 1 where a router 100, including one or more input buffers 110 and one or more output buffers 120, is used to couple a corresponding number of incoming links 130 with outgoing links 140.
The quality of a communications network service, as perceived by a user, varies greatly with the state of the network. To make packet-switched networks economically viable, it is necessary to be able to guarantee quality while reducing capital investment and operating expenses.
Degradation in the perceived quality of a service can often be traced back to loss or delay of data packets at a node or switch in the network. User satisfaction can be guaranteed by managing loss and delay of packets at those nodes where congestion can occur.
Typically, users transmit bits in bursts: active periods are interspersed with periods of inactivity. The peak rate of transmission cannot exceed the link rate. The mean rate of transmission, by definition, cannot exceed the peak rate. The ratio:
            (              peak        ⁢                                  ⁢        rate            )        -          (              mean        ⁢                                  ⁢        rate            )            (          mean      ⁢                          ⁢      rate        )  is a measure of what is called the burstiness of the source.
Loss and delay of data packets at a node in the network arise from the queuing of packets in the buffers of switches or routers. Buffers are required to cope with fluctuations in the bit-rate on incoming links. However, if the buffers are too small, packets will be lost as a result of buffer overflow; if the buffers are too large, some packets will experience unacceptable delays. For a given buffer-size, loss and delay can be reduced by increasing the capacity of the outgoing link.
To eliminate packet loss entirely, it would be necessary to increase the capacity of the outgoing link to equal the sum of the capacities of the incoming links. This is prohibitively expensive. Nevertheless, it is a strategy employed sometimes by network operators who take a conservative view on assuring network quality of service.
Another known technique is based on an understanding that it is unnecessary to eliminate packet loss and unacceptable packet delay in order to give satisfactory perceived quality. It is enough to keep their frequency within predetermined bounds. These bounds are referred to as Quality of Service (QoS) targets.
The optimal way to ensure satisfactory perceived quality is to provide the minimum capacity that will guarantee the QoS targets. This minimum capacity is referred to as the Bandwidth Requirement (BWR) of the bit-stream. It lies somewhere between the mean rate and the peak-rate requirement.
The existence of a BWR and its value can be demonstrated experimentally with a router by observing the change in the frequency with which a target queuing delay in an output buffer is exceeded when the capacity of the outgoing link is varied.
The mean-rate and the peak-rate do not depend on the QoS targets. For bursty traffic, the peak-rate can be many multiples of the mean-rate. As the QoS target changes, the BWR varies between the mean and the peak rates.
For a given QoS target, the BWR depends strongly on the nature of the traffic. There is no universal multiplier than can be applied to the mean-rate or peak-rate to give the BWR for a given QoS target. The fundamental problem in providing quality of service in a data network is to determine accurately the minimum service rate at which packets of data may be removed from a buffer in a switch whilst maintaining quality of service in the data network and optimising the available bandwidth in the network. Accurate estimation of the BWR opens the way for many applications: monitoring network quality levels, QoS-sensitive service provisioning, IP call admission control, traffic-based billing and capacity planning.
A well known approach to estimating the BWR is through traffic modelling. Such an approach consists of first, choosing a statistical model of the traffic; second, fitting the parameters of the model to the traffic; third, performing a mathematical analysis of the model to determine its queuing properties and hence its bandwidth requirement. Such methods often use what is termed an effective bandwidth analysis. Examples of these known techniques are given in “Effective bandwidths for multiclass Markov fluids and other ATM sources,” George Kesidis, Jean Walrand and Cheng-Shang Chang, IEEE/ACM Tran. Networking, Vol. 1, pp. 424-428, 1993, “Effective bandwidth estimation and testing for Markov sources”, J Pechiar, G Perera, M Simon, Performance Evaluation archive, Volume 48, Issue 1-4 (May 2002), pp 157-175 and “Traffic characterisation and effective bandwidths for broadband network traces”, R. J. Gibbens, in: F. P. Kelly, S. Zachary, I. B. Ziedins (Eds.), Stochastic Networks: Theory and Applications, Oxford University Press, Oxford, 1996, pp. 1-11.
Each of these steps is fraught, particularly the first and third. Choosing a good model is difficult: network traffic is very complex in behaviour and simple statistical models do not suffice to describe it. However, the more sophisticated the model, the more difficult it is to analyse; realistic traffic models are generally intractable. It will be appreciated also that the more sophisticated the model, the higher the computational requirement within the computer that is used to analyse and monitor the traffic flow.
This approach requires the exercise to be repeated for each new source of traffic. Furthermore, the whole procedure is limited to traffic that is stable in behaviour over the lifetime of the exercise—at least weeks—and therefore completely precludes a dynamic on-line implementation.
Practical methods of estimating the BWR typically rely on making certain statistical assumptions about the traffic flow. One such method has been described in the U.S. Pat. No. 6,580,691 (Bjoerkman et al), namely a polygonal approximation to a scaled cumulant generating function (sCGF). This US patent Specification discloses a method and system for estimating the sCGF on-line in real time and using it to estimate the BWR. The statistical assumptions made by the sCGF method assume a particular relationship between a quality target (such as a packet delay) and the frequency with which that target is exceeded: for example, it is assumed that the probability of a delay target being exceeded becomes smaller exponentially as that delay target increases. This relationship is exploited in the production of a compact traffic descriptor. The assumption is well founded but is not always accurate across the whole range of relevant quality targets. For example, at small delay targets, the probability of exceeding a delay target is governed by the time taken to serialise the data onto the link; at long delay targets or low probabilities there will be insufficient data to produce reliable statistics.
It will be appreciated that the most accurate method of determining the BWR is to record the precise details of the traffic flow and then to simulate the passage of the traffic flow through a switch, varying the simulated service rate until the QoS targets are precisely satisfied. This method is however computationally expensive and impractical to deploy.